Linked List: It consists of a
sequence of nodes (memory spaces), each
containing arbitrary data fields and one or two references ("links")
pointing to the next and/or previous nodes.
Array |
ArrayList |
Linked List |
Array is fixed size |
Size can change |
Size can change |
An array element can be accessed directly by its index |
An arraylist element can also be accessed by its index directly |
Each element cannot be accessed directly. Nodes in a linked list must be accessed sequentially |
Array elements are adjacent in memory |
Elements adjacent in memory |
Nodes may not be adjacent to each other |
No new element can be added |
To add or remove an element all existing elements need to be shifted to one side |
Add or remove can be done without shifting elements |
Self-referential class: A class that includes an instance variable or variables that can hold a reference to an object of the same class.
public class LLStringNode {
private String
info;
private LLStringNode next;
public LLStringNode(String info)
{
this.info = info;
next = null;
}
}
Question: What is the
consequence of the following line?
LLStringNode
node1 = new LLStringNode(“Hanna”);
SEE class LLStringNode.java.
public LLStringNode(String
info, LLStringNode refNode){
this.info = info;
next
= refNode;
}
Suppose you have a linked list named letters. How will you traverse all the nodes in that list?
Question: Refine this algorithm gradually to convert it
to a piece of code
public void Traverse() {
LLStringNode
currNode = letters;
//NOTE: You DON’T create a new node using constructor.
while
( currNode != null) {
//You can do whatever you
like
System.out.println(currNode.info);
currNode = currNode.next; //Advance towards the next node
}
}
v Pitfall: Falling off the End of a List
§ If currNode is at the end of the list and you execute currNode = currNode.next; currNode will be set to null. You are now at the end of the list. If you execute this statement again, it will give you an error.
LLStringNode newNode = new LLStringNode(“Barbara”);
newNode.next = letters;
letters = newNode;
letters = letters.next;